#include <iostream>
#include <vector>
#include <windows.h>

struct ListNode
{
    int val;
    ListNode * next;
    ListNode() : val(0), next(nullptr)
    {}
    ListNode(int val) : val(val), next(nullptr)
    {}
    ListNode(int val, ListNode * next) : val(val), next(next)
    {}
};


class Solution 
{
public:
    ListNode *detectCycle(ListNode *head) 
    {
        if(head == nullptr || head->next == nullptr || head->next->next == nullptr)
        {
            return nullptr;
        }
        ListNode * slow = head->next;
        ListNode * fast = head->next->next;
        while(fast != slow)
        {
            if(fast->next == nullptr || fast->next->next == nullptr)
            {
                return nullptr;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = head;
        while (fast != slow)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

// 辅助函数：创建链表节点
ListNode* createNode(int val) {
    return new ListNode(val);
}

// 辅助函数：创建有环的链表
ListNode* createCyclicList(const std::vector<int>& values, int cyclePos) {
    if (values.empty()) return nullptr;

    ListNode* head = nullptr;
    ListNode* tail = nullptr;
    ListNode* cycleNode = nullptr;
    std::vector<ListNode*> nodes;

    // 创建所有节点
    for (int i = 0; i < values.size(); ++i) {
        ListNode* node = createNode(values[i]);
        nodes.push_back(node);

        if (i == 0) {
            head = node;
        } else {
            tail->next = node;
        }
        tail = node;

        // 记录环的入口节点位置
        if (i == cyclePos) {
            cycleNode = node;
        }
    }

    // 如果cyclePos有效，创建环
    if (cyclePos >= 0 && cyclePos < values.size()) {
        tail->next = cycleNode;
    }

    return head;
}

// 辅助函数：打印链表（注意：有环的链表会无限循环，这里只打印有限长度）
void printList(ListNode* head, int maxLen = 20) {
    ListNode* current = head;
    int count = 0;
    std::cout << "链表: ";
    while (current != nullptr && count < maxLen) {
        std::cout << current->val;
        current = current->next;
        if (current != nullptr && count < maxLen - 1) {
            std::cout << " -> ";
        }
        count++;
    }
    if (count >= maxLen) {
        std::cout << " ... (可能有环)";
    }
    std::cout << std::endl;
}

// 测试函数
void testDetectCycle() {
    Solution solution;

    std::cout << "=== LeetCode 142. 环形链表 II 测试 ===\n" << std::endl;

    // 测试案例1：有环的链表，环在中间
    std::cout << "测试案例1：有环链表，环在中间" << std::endl;
    std::vector<int> values1 = {3, 2, 0, -4};
    int cyclePos1 = 1; // 环从索引1开始（节点值为2）
    ListNode* head1 = createCyclicList(values1, cyclePos1);
    printList(head1);
    ListNode* cycleNode1 = solution.detectCycle(head1);
    if (cycleNode1 != nullptr) {
        std::cout << "环的入口节点值: " << cycleNode1->val << std::endl;
        std::cout << "期望值: 2" << std::endl;
        std::cout << (cycleNode1->val == 2 ? "✓ 通过" : "✗ 失败") << std::endl;
    } else {
        std::cout << "未找到环 ✗ 失败" << std::endl;
    }
    std::cout << std::endl;

    // 测试案例2：有环的链表，环在开头（整个链表是一个环）
    std::cout << "测试案例2：有环链表，环在开头" << std::endl;
    std::vector<int> values2 = {1, 2, 3, 4};
    int cyclePos2 = 0; // 环从索引0开始
    ListNode* head2 = createCyclicList(values2, cyclePos2);
    printList(head2);
    ListNode* cycleNode2 = solution.detectCycle(head2);
    if (cycleNode2 != nullptr) {
        std::cout << "环的入口节点值: " << cycleNode2->val << std::endl;
        std::cout << "期望值: 1" << std::endl;
        std::cout << (cycleNode2->val == 1 ? "✓ 通过" : "✗ 失败") << std::endl;
    } else {
        std::cout << "未找到环 ✗ 失败" << std::endl;
    }
    std::cout << std::endl;

    // 测试案例3：无环链表
    std::cout << "测试案例3：无环链表" << std::endl;
    std::vector<int> values3 = {1, 2, 3, 4, 5};
    int cyclePos3 = -1; // 无环
    ListNode* head3 = createCyclicList(values3, cyclePos3);
    printList(head3);
    ListNode* cycleNode3 = solution.detectCycle(head3);
    if (cycleNode3 == nullptr) {
        std::cout << "正确检测到无环 ✓ 通过" << std::endl;
    } else {
        std::cout << "错误检测到环，实际节点值: " << cycleNode3->val << " ✗ 失败" << std::endl;
    }
    std::cout << std::endl;

    // 测试案例4：单节点有环
    std::cout << "测试案例4：单节点有环" << std::endl;
    std::vector<int> values4 = {1};
    int cyclePos4 = 0; // 单节点指向自己
    ListNode* head4 = createCyclicList(values4, cyclePos4);
    printList(head4);
    ListNode* cycleNode4 = solution.detectCycle(head4);
    if (cycleNode4 != nullptr) {
        std::cout << "环的入口节点值: " << cycleNode4->val << std::endl;
        std::cout << "期望值: 1" << std::endl;
        std::cout << (cycleNode4->val == 1 ? "✓ 通过" : "✗ 失败") << std::endl;
    } else {
        std::cout << "未找到环 ✗ 失败" << std::endl;
    }
    std::cout << std::endl;

    // 测试案例5：空链表
    std::cout << "测试案例5：空链表" << std::endl;
    ListNode* head5 = nullptr;
    ListNode* cycleNode5 = solution.detectCycle(head5);
    if (cycleNode5 == nullptr) {
        std::cout << "正确检测到空链表无环 ✓ 通过" << std::endl;
    } else {
        std::cout << "错误检测到环 ✗ 失败" << std::endl;
    }
    std::cout << std::endl;

    // 清理内存
    // 注意：实际使用中应该释放链表内存，这里为了简化测试就省略了
}

int main() {
    SetConsoleOutputCP(CP_UTF8);
    testDetectCycle();
    return 0;
}